package com.wtgroup.demo.leetcode.q023_合并K个升序链表;

import com.wtgroup.demo.common.bean.LinkNode;

/**
 * @author 60906
 * @date 2021/5/6 11:54
 */
public class Q023_Test {


    /**
     * LC 归并是自下而上的, 我这里尝试逻辑更直白的自上而下.
     */
    private class Solution_MyMerge {

        public LinkNode mergeKLists(LinkNode[] lists) {
            if (lists==null || lists.length==0) {
                return null;
            }
            return func(lists, 0, lists.length - 1);
        }

        private LinkNode func(LinkNode[] lists, int left, int right) {
            if (right==left) {
                return lists[left];
            }

            int mid = (left+right) / 2;
            LinkNode l1 = func(lists, left, mid);
            LinkNode l2 = func(lists, mid + 1, right);
            return merge(l1, l2);
        }

        // 合并两个有序链表
        private LinkNode merge(LinkNode l1, LinkNode l2) {

            LinkNode dummyHead = new LinkNode();
            LinkNode tail = dummyHead;
            while (l1 != null && l2 != null) {
                if (l1.value <= l2.value) {
                    tail.next = l1;
                    l1 = l1.next;
                } else {
                    tail.next = l2;
                    l2 = l2.next;
                }
                tail = tail.next;
            }
            tail.next = l1 != null ? l1 : l2;
            return dummyHead.next;
        }


    }


}
